Статья 4121

Название статьи

Построение оптимального остовного дерева как инструмент для обеспечения устойчивости сети связи 

Авторы

Борис Феликсович Мельников, доктор физико-математических наук, профессор факультета вычислительной математики и кибернетики, Совместный университет МГУ–ППИ в Шэньчжэне (Китай, 517182, Провинция Гуандун, г. Шэньчжэнь, район Лунган, Даюньсиньчэн, ул. Гоцзидасюеюань, 1), E-mail: bormel@mail.ru
Юлия Юрьевна Терентьева, кандидат технических наук, начальник управления анализа и методологии совершенствования информационных телекоммуникационных систем, Центр информационных технологий и систем органов государственной власти (Россия, г. Москва, Пресненский Вал, 19, стр. 1), E-mail: terjul@mail.ru 

Индекс УДК

004.023+519.173.1. 

DOI

10.21685/2072-3059-2021-1-4 

Аннотация

Актуальность и цели. При проектировании/модернизации и эксплуатации сетей связи одной из самых главных задач является обеспечение ее устойчивости. Реальные сети связи часто имеют высокую размерность, и, соответственно, при их проектировании и модернизации для экономии ресурсов важно получать решения, как можно более близкие к оптимальным. Устойчивость сети связи непосредственно связана с количеством независимых маршрутов между вершинами моделирующего графа, описывающего информационные направления связи. Авторами рассмотрен вопрос разработки алгоритмов построения независимых путей и показана эффективность использования процедур формирования оптимального остовного дерева для решения задачи обеспечения устойчивости сети связи. Цель исследования: разработка алгоритмов построения оптимальных независимых путей между заданными вершинами графа с целью обеспечения требуемой живучести сети связи при минимизации затрат на модернизацию топологии сети связи.
Материалы и методы. Используются алгоритмы теории графов, как известные, так и вновь разработанные. В частности, рассматриваются жадные алгоритмы, а также другие эвристические алгоритмы.
Результаты. Разработаны эвристические алгоритмы построения оптимальных независимых путей между заданными вершинами графа сети связи, показана эффективность использования подхода формирования оптимального остовного дерева для решения задачи обеспечения устойчивости сети связи.
Выводы. Было предложено улучшение алгоритмов построения оптимального остовного дерева, которое использовалось при построении независимых путей между вершинами графа и показана эффективность использования процедур формирования остовного дерева для решения задачи обеспечения устойчивости сети связи. 

Ключевые слова

устойчивость сети связи, граф сети связи, эвристические алгоритмы 

 

 Скачать статью в формате PDF

Список литературы

1. Melnikov B. F., Meshchanin V. Y., Terentyeva Y. Y. Implementation of optimality criteria in the design of communication networks // Journal of Physics: Conference Series, International Scientific Conference ICMSIT–2020 : Metrological Support of Innovative Technological, ICMSIT-2020 (paper 3095). http://conf.domnit.ru/en/ conferences/icmsit-2020-en/
2. Булынин А. Г., Мельников Б. Ф., Мещанин В. Ю., Терентьева Ю. Ю. Оптимизационные задачи, возникающие при проектировании сетей связи высокой размерности, и некоторые эвристические методы их решения // Информатизация и связь. 2020. № 1. С. 34–40. URL: https://elibrary.ru/item.asp?id=42839357
3. Булынин А. Г., Мельников Б. Ф., Мещанин В. Ю., Терентьева Ю. Ю. Алгоритмы проектирования сетей связи с применением жадных эвристик разных типов // Информационные технологии и нанотехнологии (ИТНТ-2020) : сб. тр. по материалам VI Междунар. конф. и молодежной школы. Самара, 2020. С. 856–860. URL: https://www.elibrary.ru/item.asp?id=43576630
4. Kruskal J. On the shortest spanning subtree of a graph and the traveling salesman problem // Proceedings of the American Mathematical Society. 1956. Vol. 7, № 1. P. 48–50. doi:10.1090/S0002-9939-1956-0078686-7
5. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы. Построение и анализ. Москва : Вильямс, 2005. 1296 с.
6. Goodrich M., Tamassia R. Data Structures and Algorithms in Java, Fourth Edition. N.J. : John Wiley & Sons, 2006.
7. Prim R. Shortest connection networks and some generalizations // Bell System Technical Journal. 1957. Vol. 36, № 6. P. 1389–1401. doi:10.1002/j.1538-7305.1957.tb01515
8. Мельников Б. Ф., Терентьева Ю. Ю. Построение коммуникационных сетей: о применении алгоритма Краскала в задачах больших размерностей // International Journal of Open Information Technologies. 2021. Vol. 9, № 1. С.13–21.
9. Оре О. Теория графов. М. : Мир, 1980. 

 

Дата создания: 04.02.2021 09:02
Дата обновления: 12.05.2021 15:18